package ljl.alg.wangzheng_camp.round1.hashmap;

import java.util.HashSet;
import java.util.Set;

/*
* 给定两个整数数组，请交换一对数值（每个数组中取一个数值），使得两个数组所有元素的和相等。

返回一个数组，第一个元素是第一个数组中要交换的元素，第二个元素是第二个数组中要交换的元素。
* 若有多个答案，返回任意一个均可。若无满足条件的数值，返回空数组。

示例:

输入: array1 = [4, 1, 2, 1, 1, 2], array2 = [3, 6, 3, 3]
输出: [1, 3]
示例:

输入: array1 = [1, 2, 3], array2 = [4, 5, 6]
输出: []
* */
public class _16_21_swap_sum {
    
    int[] NONE = new int[0];
    public int[] findSwapValues(int[] array1, int[] array2) {
        Set<Integer> set2 = new HashSet<>();
        int sum1 = 0;
        for (int j : array1) {
            sum1 += j;
        }
        int sum2 = 0;
        for (int j : array2) {
            sum2 += j;
            set2.add(j);
        }
        int sum = sum1 + sum2;
        if (sum % 2 != 0) return NONE;
        int dif = sum1 - sum / 2;
        /*
        * (sum1 - sum2) / 2 = (sum1 - sum1 / 2 - sum2 / 2)
        * 居然 dif 可以直接用做差来获取，不用求和再搞
        * */
        // 两个 dif 加起来是 0？ sum1 - sum/2 + sum2 - sum/2 == 0
        // 交换，就是 sum1 - x + y = sum / 2，
        // 就是 x - y = sum1 - sum / 2;
        // 就是 x - y = dif
        for (int each : array1) {
            if (set2.contains(each - dif)) return new int[] {each, each - dif};
        }
        return NONE;
    }
    
//  这是代码来源
    /*
    * def findSwapValues(self, array1: List[int], array2: List[int]) -> List[int]:
    *     diff = sum(array1) - sum(array2)
    *     if diff & 1: return []
    *     diff >>= 1
    *     s2 = set(array2)
    *     for a in array1:
    *         if a - diff in s2:
    *             return [a, a - diff]
    *     return []
    * */
}
